package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/10/20 21:34
 */
public class CountNodes_222 {

    // 记录有多少个结点应该减去
    int count = 0;

    // 当发现有非空底层结点时，置为true
    boolean find = false;

    public int countNodes(TreeNode root) {
        int height = 1;
        if (root == null) return 0;
        // 求高度
        TreeNode left = root.left;
        while (left != null) {
            height++;
            left = left.left;
        }
        countLeaves(root, 0, height);
        // 用公式计算值，减去不需要计入的节点数量
        return (int) Math.pow(2, height) - count - 1;
    }

    // 从右往左进行遍历，采用中序的方式，结合剪枝
    private void countLeaves(TreeNode root, int h, int height) {
        // 如果之前已经找到，或者已经到达底层，那么直接退出
        if (find || h == height) {
            return;
        }
        // 从右向左 -- 因为完全二叉树优先填满左边
        countLeaves(root.right, h + 1, height);
        if (h == height - 1) {
            // 如果是空节点，那么+2，并且不对find进行赋值
            if (root.left == null && root.right == null) {
                count += 2;
            } else if (root.left == null || root.right == null) {
                // 当结点只有一个子节点，count + 1，并且左边的所有结点都是非空结点，并且左边的所有结点要么不存在，要么都有两个子节点
                count++;
                find = true;
            } else {
                // 恰好找了一个有两个子节点的节点，直接赋值
                find = true;
            }
            return;
        }
        countLeaves(root.left, h + 1, height);
    }
}
